home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / zip.zip / IM_CTREE.C < prev    next >
C/C++ Source or Header  |  1992-09-22  |  46KB  |  1,402 lines
  1. /*
  2.  
  3.  Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
  4.  Permission is granted to any individual or institution to use, copy, or
  5.  redistribute this software so long as all of the original files are included
  6.  unmodified, that it is not sold for profit, and that this copyright notice
  7.  is retained.
  8.  
  9. */
  10.  
  11. /*
  12.  *  im_ctree.c by Richard B. Wales.
  13.  *
  14.  *  Includes modifications by Jean-Loup Gailly.
  15.  *
  16.  *  PURPOSE
  17.  *
  18.  *      Encode various sets of source values using variable-length
  19.  *      binary code trees.
  20.  *
  21.  *  DISCUSSION
  22.  *
  23.  *      The PKZIP "implosion" process uses several variable-depth binary
  24.  *      code trees, similar to Huffman trees.  The more common source
  25.  *      values are represented by shorter bit sequences.
  26.  *
  27.  *      Each code tree is stored in the ZIP file in a compressed form
  28.  *      that is essentially a run-length-encoded list of the lengths of
  29.  *      all the code strings (in ascending order by source values).
  30.  *      The actual code strings are reconstructed from the lengths in
  31.  *      the UNZIP process, as described in the "application note"
  32.  *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
  33.  *
  34.  *      Because of the way a code tree is stored in the ZIP file, the
  35.  *      codes must conform to the following restrictions:
  36.  *
  37.  *      (1) No code string may ever exceed 16 bits in length.
  38.  *
  39.  *      (2) If all code strings are extended to 16 bits by padding on
  40.  *          the right (low-order end) with zeros, and then treated as
  41.  *          unsigned 16-bit integers, then:
  42.  *
  43.  *          (a) The arithmetically higher 16-bit values must correspond
  44.  *              to the shorter code strings.
  45.  *
  46.  *          (b) If two source values map into code strings of the same
  47.  *              length, the higher code string must correspond to the
  48.  *              lower source value (where source values are treated as
  49.  *              unsigned).
  50.  *
  51.  *      Further, shortcuts taken by PKUNZIP 1.10 in the way it decodes
  52.  *      the compressed data via the trees impose the following extra
  53.  *      limitations:
  54.  *
  55.  *      (3) No code string in the "distance" tree can be longer than 8
  56.  *          bits.
  57.  *
  58.  *      (4) The maximum length of any code string is limited by the
  59.  *          number of initial zero bits, as follows:
  60.  *
  61.  *          (a) 0-3 leading zeros:  maximum length is 8.
  62.  *
  63.  *          (b) 4-5 leading zeros:  maximum length is 12.
  64.  *
  65.  *          (c) 6-7 leading zeros:  maximum length is 14.
  66.  *
  67.  *      (5) In the "literal" tree, the code string corresponding to the
  68.  *          source value 255 must be at least 10 bits in length, regard-
  69.  *          less of the frequency of the value 255 in the file.
  70.  *
  71.  *      PKWARE calls the code trees "Shannon-Fano trees".  (Shannon-Fano
  72.  *      coding was a predecessor to the better-known Huffman coding
  73.  *      technique; see the references below.)  Although it appears that
  74.  *      the Shannon-Fano (top-down partitioning) algorithm is in fact
  75.  *      used by PKZIP in the process of creating the code trees, the
  76.  *      resulting trees are not in fact "pure" Shannon-Fano, because of
  77.  *      the extra processing required in order to meet the restrictions
  78.  *      described above.
  79.  *
  80.  *  REFERENCES
  81.  *
  82.  *      Lynch, Thomas J.
  83.  *          Data Compression:  Techniques and Applications, pp. 53-55.
  84.  *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
  85.  *
  86.  *      Storer, James A.
  87.  *          Data Compression:  Methods and Theory, pp. 49-50.
  88.  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
  89.  *
  90.  *  INTERFACE
  91.  *
  92.  *      ImpErr ct_init (void)
  93.  *          Initialize the code tree routines.  This routine must be
  94.  *          called before any other code tree routines may be called.
  95.  *
  96.  *      ImpErr ct_tally (MATCH *ma)
  97.  *          Tally a "string match" data set.  The tally results will be
  98.  *          used to determine how large the imploded result will be.
  99.  *
  100.  *      ImpErr ct_mktrees (FDATA *fd)
  101.  *          Construct all code trees, and then determine how big the
  102.  *          imploded file will be under both "literal tree" and "no
  103.  *          literal tree" conditions.  Choose the best option.
  104.  *
  105.  *      ImpErr ct_wrtrees (FILE *outfp)
  106.  *          Output the code trees to the ZIP file.
  107.  *
  108.  *      ImpErr ct_wrdata (FILE *outfp)
  109.  *          Output the file data to the ZIP file.
  110.  *
  111.  *      ImpErr ct_windup (void)
  112.  *          Deallocate all code trees.
  113.  */
  114.  
  115.  
  116. #ifdef DEBUG
  117. #   define VALIDATE
  118. #endif /* DEBUG */
  119.  
  120. #include "implode.h"
  121.  
  122.  
  123. /***********************************************************************
  124.  *
  125.  * Local data used by the "code tree" routines.
  126.  */
  127.  
  128.  
  129. /* Data structure describing a single value and its code string. */
  130. typedef
  131. struct  ct_data
  132.     {   UL_INT  ct_freq;                /* frequency count */
  133.         US_INT  ct_code;                /* bit string */
  134.         U_CHAR  ct_len;                 /* length of bit string */
  135.         U_CHAR  ct_val;                 /* source value */
  136.     }
  137.     TRDATA;
  138.  
  139.  
  140. /*
  141.  * Data structure for re-sorting source values by bit string length;
  142.  * used during tree generation.
  143.  */
  144. typedef
  145. struct  ct_resort
  146.     {   U_CHAR  ct_rlen;                /* length of bit string */
  147.         U_CHAR  ct_rval;                /* source value */
  148. #ifdef VMS
  149.         US_INT  dummy;                  /* because of bug in qsort() */
  150. #endif /* VMS */
  151.     }
  152.     RESORT;
  153.  
  154.  
  155. /* Header for a code tree. */
  156. typedef
  157. struct  ct_desc
  158.     {   TRDATA *ct_array;               /* array of TRDATA */
  159.         int     ct_size;                /* # of entries in tree */
  160.     }
  161.     TRDESC;
  162.  
  163.  
  164. /*
  165.  * Currently active code trees.
  166.  * We allow for five trees (one literal tree, two length trees, and
  167.  * two distance trees) so that we can evaluate the total compression
  168.  * with or without the use of the literal tree.  Remember that the
  169.  * minimum matching distance depends on whether or not a literal tree
  170.  * is used; hence, the "length" and "distance" trees will differ.
  171.  */
  172. #define MAXTREES        5               /* max # of trees at once */
  173. local   TRDESC  ct_table[MAXTREES];
  174.  
  175.  
  176. /* Macro to validate a code tree handle. */
  177. #define VALID_HANDLE(x) \
  178.         ((x) >= 0 && (x) < MAXTREES && ct_table[x].ct_array != NULL)
  179.  
  180.  
  181. /*
  182.  * Assorted frequency counts.
  183.  * The "Minimum Match Length" (MML) is 2 if a "literal character" code
  184.  * tree is not used, or 3 if a "literal character" tree is used.  Thus,
  185.  * we need to keep two sets of "length" and "distance" frequency counts.
  186.  * Also, 2-character matches need to be counted separately; depending
  187.  * on whether a "literal character" tree is used or not, these will be
  188.  * processed either as literal characters or as distance/length pairs.
  189.  */
  190.  
  191. /* Total number of source values from Pass One. */
  192. local   long    ct_litc_num;            /* total # literal chars */
  193. local   long    ct_lit2_num;            /* total # of 2-char matches */
  194. local   long    ct_strg_num;            /* total # of string matches */
  195.  
  196. /* Source value frequencies for the five trees. */
  197. local   long    ct_litc_freq[256];      /* literal character freqs */
  198. local   long    ct_len2_freq[64];       /* length freqs (MML=2) */
  199. local   long    ct_len3_freq[64];       /* length freqs (MML=3) */
  200. local   long    ct_dst2_freq[64];       /* distance freqs (MML=2) */
  201. local   long    ct_dst3_freq[64];       /* distance freqs (MML=3) */
  202.  
  203. /* Number of bits saved by using each of the trees. */
  204. local   long    ct_litc_saved;          /* literal tree */
  205. local   long    ct_len2_saved;          /* length tree (MML=2) */
  206. local   long    ct_len3_saved;          /* length tree (MML=3) */
  207. local   long    ct_dst2_saved;          /* distance tree (MML=2) */
  208. local   long    ct_dst3_saved;          /* distance tree (MML=3) */
  209.  
  210. /* Handles for the code trees to be used. */
  211. local   int     ct_litc_tree;           /* temp literal tree */
  212. local   int     ct_len2_tree;           /* temp length tree (MML=2) */
  213. local   int     ct_len3_tree;           /* temp length tree (MML=3) */
  214. local   int     ct_dst2_tree;           /* temp distance tree (MML=2) */
  215. local   int     ct_dst3_tree;           /* temp distance tree (MML=3) */
  216. local   int     lit_tree;               /* literal tree (-1 if none) */
  217. local   int     len_tree;               /* length tree */
  218. local   int     dst_tree;               /* distance tree */
  219.  
  220.  
  221. /***********************************************************************
  222.  *
  223.  * Local (static) routines in this file.
  224.  */
  225.  
  226. local ImpErr ct_alloc
  227.         OF ((int size, int *handle));
  228.  
  229. local ImpErr ct_free
  230.         OF ((int handle));
  231.  
  232. local ImpErr ct_loadf
  233.         OF ((int handle, long *freq));
  234.  
  235. local ImpErr ct_ziprep
  236.         OF ((int handle, U_CHAR **result));
  237.  
  238. local ImpErr ct_gencodes
  239.         OF ((int handle, int minbits, int maxbits, long *saved));
  240.  
  241. local ImpErr ct_split
  242.         OF ((TRDATA *part, int size, long freq,
  243.              int prefix, int preflen, int minbits, int maxbits));
  244.  
  245. local int ct_fsort
  246.         OF ((TRDATA *tr1, TRDATA *tr2));
  247.  
  248. local int ct_rsort
  249.         OF ((RESORT *cr1, RESORT *cr2));
  250.  
  251.  
  252. /***********************************************************************
  253.  *
  254.  * Allocate a code tree.
  255.  */
  256.  
  257. local
  258. ImpErr
  259. ct_alloc (size, handle)
  260.     int size;
  261.     int *handle;
  262. {   register TRDATA *ct;
  263.     int n;
  264.  
  265. #ifdef VALIDATE
  266.     /* Validate the arguments. */
  267.     if (size < 2 || size > 256) goto badarg;
  268.     if (handle == NULL)         goto badarg;
  269. #endif /* VALIDATE */
  270.  
  271.     /* Allocate an available code tree handle. */
  272.     for (n = 0;
  273.          n < MAXTREES && ct_table[n].ct_array != NULL;
  274.          n++) ;
  275.     if (n >= MAXTREES) return IM_NOCTBLS;
  276.     *handle = n;
  277.     ct_table[n].ct_size  = size;
  278.  
  279.     /* Allocate space for the code tree. */
  280.     ct = (TRDATA *) malloc ((unsigned) (size * sizeof (TRDATA)));
  281.     if (ct == NULL) return IM_NOMEM;
  282.     ct_table[n].ct_array = ct;
  283.  
  284.     /* Initialize the code tree. */
  285.     for (n = 0; n < size; n++, ct++)
  286.     {   ct->ct_freq = 0;
  287.         ct->ct_code = 0;
  288.         ct->ct_val  = (U_CHAR)n;
  289.         ct->ct_len  = 0;
  290.     }
  291.  
  292.     /* That's all. */
  293.     return IM_OK;
  294.  
  295. #ifdef VALIDATE
  296. badarg:
  297.     fprintf (stderr, "\nError in ct_alloc: bad argument(s)");
  298.     return IM_BADARG;
  299. #endif /* VALIDATE */
  300. }
  301.  
  302.  
  303. /***********************************************************************
  304.  *
  305.  * Free a code tree.
  306.  */
  307.  
  308. local
  309. ImpErr
  310. ct_free (handle)
  311.     int handle;
  312. {
  313. #ifdef VALIDATE
  314.     /* Validate the argument. */
  315.     if (!VALID_HANDLE (handle)) goto badarg;
  316. #endif /* VALIDATE */
  317.  
  318.     /* Free the code tree. */
  319.     free ((char *) ct_table[handle].ct_array);
  320.     ct_table[handle].ct_array = NULL;
  321.     ct_table[handle].ct_size  = 0;
  322.  
  323.     /* That's all. */
  324.     return IM_OK;
  325.  
  326. #ifdef VALIDATE
  327. badarg:
  328.     fprintf (stderr, "\nError in ct_free: bad argument(s)");
  329.     return IM_BADARG;
  330. #endif /* VALIDATE */
  331. }
  332.  
  333.  
  334. /***********************************************************************
  335.  *
  336.  * Update a code tree with frequency data.
  337.  *
  338.  * In order to allow for the later addition of "adaptive" coding,
  339.  * the new frequencies are added to the existing data.
  340.  */
  341.  
  342. local
  343. ImpErr
  344. ct_loadf (handle, freq)
  345.     int   handle;
  346.     long *freq;
  347. {   register long *f;
  348.     register TRDATA *ct;
  349.     int n;
  350.  
  351. #ifdef VALIDATE
  352.     /* Validate the arguments. */
  353.     if (!VALID_HANDLE (handle)) goto badarg;
  354. #endif /* VALIDATE */
  355.  
  356.     /* Add in the frequencies. */
  357.     for (f = freq,
  358.              ct = ct_table[handle].ct_array,
  359.              n = ct_table[handle].ct_size;
  360.          n > 0;
  361.          f++, ct++, n--)
  362.         ct->ct_freq += *f;
  363.  
  364.     /* That's all. */
  365.     return IM_OK;
  366.  
  367. #ifdef VALIDATE
  368. badarg:
  369.     fprintf (stderr, "\nError in ct_loadf: bad argument(s)");
  370.     return IM_BADARG;
  371. #endif /* VALIDATE */
  372. }
  373.  
  374.  
  375. /***********************************************************************
  376.  *
  377.  * Generate the ZIP-file representation for a code tree.
  378.  *
  379.  * The returned "result" value points to static data which will be
  380.  * overwritten on the next call to "ct_ziprep".
  381.  *
  382.  * The length of the result string is implicit in the first byte of
  383.  * the value, as specified in the PKZIP applications note.
  384.  */
  385.  
  386. #ifdef IMPDEBUG
  387. char *treename;
  388. #endif /* IMPDEBUG */
  389.  
  390. local
  391. ImpErr
  392. ct_ziprep (handle, result)
  393.     int      handle;
  394.     U_CHAR **result;
  395. {   static U_CHAR buffer[257];          /* result info */
  396.     register U_CHAR *c;
  397.     register TRDATA *ct;
  398.     int s, n, l;
  399.  
  400. #ifdef VALIDATE
  401.     /* Validate the arguments. */
  402.     if (!VALID_HANDLE (handle)) goto badarg;
  403.     if (result == NULL)         goto badarg;
  404. #endif /* VALIDATE */
  405.  
  406. #ifdef  IMPDEBUG
  407.     if (treename != NULL && treename[0] != 0)
  408.     {   /* Print the code tree info. */
  409.         fprintf (stderr, "\n%s tree:\n  value      len   string\n",
  410.                  treename);
  411.         for (ct = ct_table[handle].ct_array,
  412.                   s = ct_table[handle].ct_size,
  413.                   n = 0;
  414.              s > 0;
  415.              ct++, n++, s--)
  416.             fprintf (stderr, "  %3d (%02x)    %2d    %04x (rev %04x)\n",
  417.                      n, n, ct->ct_len,
  418.                      bi_reverse(ct->ct_code << (16 - ct->ct_len),
  419.                                 ct->ct_len) << (16 - ct->ct_len),
  420.                      ct->ct_code);
  421.     }
  422. #endif  /* IMPDEBUG */
  423.  
  424.     /* Generate the returned value. */
  425.     for (c = buffer+1,
  426.              ct = ct_table[handle].ct_array,
  427.              s = ct_table[handle].ct_size,
  428.              n = 0,
  429.              l = ct->ct_len;
  430.          s > 0;
  431.          ct++, s--)
  432.     {   if (l < 1 || l > 16)
  433.         {   fprintf (stderr, "\nError in ct_ziprep: bad code length");
  434.             return IM_LOGICERR;
  435.         }
  436.         if (n >= 16 || (int)ct->ct_len != l)
  437.         {   *c++ = (U_CHAR)((((n-1) << 4) & 0xf0) | ((l-1) & 0x0f));
  438.             n = 1; l = ct->ct_len;
  439.         }
  440.         else n++;
  441.     }
  442.     if (n > 0)
  443.         *c++ = (U_CHAR)((((n-1) << 4) & 0xf0) | ((l-1) & 0x0f));
  444.     buffer[0] = (U_CHAR)((c - buffer) - 2);
  445.  
  446.     /* That's all. */
  447.     *result = buffer;
  448.     return IM_OK;
  449.  
  450. #ifdef VALIDATE
  451. badarg:
  452.     fprintf (stderr, "\nError in ct_ziprep: bad argument(s)");
  453.     return IM_BADARG;
  454. #endif /* VALIDATE */
  455. }
  456.  
  457.  
  458. /***********************************************************************
  459.  *
  460.  * Look up the code string for a given value.
  461.  */
  462.  
  463. #define ct_lookup(handle, value, string, length) \
  464. {   register TRDATA *ct; \
  465.     ct = ct_table[handle].ct_array + (value); \
  466.     string = ct->ct_code; \
  467.     length = ct->ct_len; \
  468. }
  469.  
  470.  
  471. /***********************************************************************
  472.  *
  473.  * Generate the codes for a code tree.  If old codes already exist for
  474.  * the tree, they are discarded, and a new set of codes is generated
  475.  * from scratch.
  476.  * IN assertion: ma_buf is already allocated and can be overwritten.
  477.  */
  478.  
  479. local
  480. ImpErr
  481. ct_gencodes (handle, minbits, maxbits, saved)
  482.     int   handle;                       /* which tree */
  483.     int   minbits;                      /* min code string bit length */
  484.     int   maxbits;                      /* max code string bit length */
  485.     long *saved;                        /* how many bits saved */
  486. {   register TRDATA *ct;
  487.     TRDATA *ct2;
  488.     register int n;
  489.     UL_INT f;
  490.     register RESORT *cr;
  491.     int code, srclen;
  492.     long totalfreq, totalbits;
  493.     ImpErr retcode;
  494.     RESORT rbuf[256];
  495.     int size; /* alias for ct_table[handle].ct_size */
  496.     int z;    /* index of zero frequency element */
  497.     int nz;   /* index of non zero frequency element */
  498.  
  499. #ifdef VALIDATE
  500.     /* Validate the arguments. */
  501.     if (!VALID_HANDLE (handle)) goto badarg;
  502.     if (minbits < 1)            goto badarg;
  503.     if (maxbits > 16)           goto badarg;
  504.     if (maxbits < minbits)      goto badarg;
  505.     if (saved == NULL)          goto badarg;
  506. #endif /* VALIDATE */
  507.     size = ct_table[handle].ct_size;
  508.  
  509.     /*
  510.      * Start by sorting the data by frequency.  The source values with
  511.      * higher frequency need to get the shorter Shannon-Fano codes.
  512.      * First exclude the elements with zero frequency, to speed up the sort.
  513.      * This optimization is very important for small files, otherwise the sort
  514.      * takes most of the implode time.
  515.      *    Also determine the total of all frequencies.  This will be needed in
  516.      * order to partition the source values in the Shannon-Fano bit
  517.      * string computation. Finally clear the "code" (bit string) and "len"
  518.      * (bit string length) fields in the code tree array.
  519.      */
  520.     totalfreq = 0;
  521.     ct = ct_table[handle].ct_array;
  522.     /* Copy ct into a tempo */
  523.     ct2 = (TRDATA*) ma_buf;
  524.     memcpy((char*)ct2, (char*)ct, size * sizeof(TRDATA));
  525.     for (nz = 0, z = n = size-1; n >= 0; n--) {
  526.         int m;
  527.         if (ct2[n].ct_freq != 0L) {
  528.             m = nz++;
  529.             totalfreq += (ct[m].ct_freq = ct2[n].ct_freq);
  530.         } else {
  531.             m = z--;
  532.             ct[m].ct_freq = 0L;
  533.         }
  534.         ct[m].ct_code = 0;
  535.         ct[m].ct_len = 0;
  536.         ct[m].ct_val = (U_CHAR)n; /* ct2[n].ct_val */
  537.     }
  538.     qsort ((char *) (ct_table[handle].ct_array), nz,
  539.            sizeof (TRDATA), (int (*)())ct_fsort);
  540.  
  541.     /*
  542.      * Generate the bit strings via a Shannon-Fano (top-down) algorithm.
  543.      */
  544.     retcode =
  545.         ct_split (ct_table[handle].ct_array,    /* partition start */
  546.                   size,                         /* partition size */
  547.                   totalfreq,                    /* total frequency */
  548.                   0,                            /* code string prefix */
  549.                   0,                            /* # bits in prefix */
  550.                   minbits,                      /* minimum tree depth */
  551.                   maxbits);                     /* maximum tree depth */
  552.     if (retcode != IM_OK) return retcode;
  553.  
  554.     /*
  555.      * The source value 255 needs to be assigned a bit string with a
  556.      * length of at least 10, in order to accommodate shortcuts in
  557.      * PKUNZIP's decoding algorithm.  If no bit string in the tree is
  558.      * of length 10, we assign 255 to the longest string and hope for
  559.      * the best.
  560.      */
  561.     n = size;
  562.     if (n == 256)
  563.     {   for (ct = ct_table[handle].ct_array;
  564.              n > 0 && ct->ct_val != 255;
  565.              n--, ct++) ;
  566.         if (n == 0)
  567.         {   fprintf (stderr, "\nError in ct_gencodes: no value 255");
  568.             return IM_LOGICERR;
  569.         }
  570.         if (ct->ct_len < 10)
  571.         {   ct2 = ct;
  572.             while (n > 0 && ct->ct_len < 10) n--, ct++;
  573.             if (n == 0) ct--;   /* no len>=10 in tree; use longest */
  574.             n = ct->ct_val;
  575.                 ct->ct_val = ct2->ct_val;
  576.                 ct2->ct_val = (U_CHAR)n;
  577.             f = ct->ct_freq;
  578.                 ct->ct_freq = ct2->ct_freq;
  579.                 ct2->ct_freq = f;
  580.     }   }
  581.  
  582.     /*
  583.      * The source values need to be re-sorted so that all source values
  584.      * with code strings of the same length will be in ascending order.
  585.      * This is because of the compression scheme used to represent the
  586.      * tree in the ZIP file.
  587.      */
  588.     for (n = size,
  589.              ct = ct_table[handle].ct_array,
  590.              cr = rbuf;
  591.          n > 0;
  592.          n--, ct++, cr++)
  593.     {   cr->ct_rlen = ct->ct_len;
  594.         cr->ct_rval = ct->ct_val;
  595.     }
  596.     n = size;
  597.     qsort ((char *) rbuf, n, sizeof (RESORT), (int (*)())ct_rsort);
  598.     for (ct = ct_table[handle].ct_array,
  599.              cr = rbuf;
  600.          n > 0;
  601.          n--, ct++, cr++)
  602.         ct->ct_val = cr->ct_rval;
  603.  
  604. #ifdef DUMP_TREE
  605.     printf ("Finished tree:\n");
  606.     for (n = size,
  607.              ct = ct_table[handle].ct_array;
  608.          n > 0;
  609.          n--, ct++)
  610.         printf ("  %3d (0x%02x)  l %2d  c 0x%04x f %ld\n",
  611.                 ct->ct_val, ct->ct_val, ct->ct_len, ct->ct_code, ct->ct_freq);
  612.     putchar ('\n');
  613. #endif /* DUMP_TREE */
  614.  
  615.     /*
  616.      * Finally, sort the tree back in ascending order by source value
  617.      * -- which is the order expected by other portions of the program.
  618.      */
  619.     ct = ct_table[handle].ct_array;
  620.     /* Copy ct into a tempo */
  621.     ct2 = (TRDATA*)ma_buf;
  622.     memcpy((char*)ct2, (char*)ct, size * sizeof(TRDATA));
  623.     for (n = size-1; n >= 0; n--) {
  624.         U_CHAR v = ct2[n].ct_val;
  625.         ct[v].ct_freq = ct2[n].ct_freq;
  626.         ct[v].ct_code = ct2[n].ct_code;
  627.         ct[v].ct_len = ct2[n].ct_len;
  628.         ct[v].ct_val = v;
  629.     }
  630.  
  631.     /*
  632.      * Determine how many bits will be saved if all the source data is
  633.      * encoded using this new set of code strings, as opposed to being
  634.      * represented directly in unencoded form.
  635.      */
  636.     /* # of bits needed for unencoded source values */
  637.     n = ct_table[handle].ct_size;
  638.     for (code = 1, srclen = 0; code < n; code <<= 1, srclen++) ;
  639.     /* # of bits used if all source values encoded via this tree */
  640.     for (ct = ct_table[handle].ct_array,
  641.              totalbits = 0;
  642.          n > 0;
  643.          n--, ct++)
  644.         totalbits += ct->ct_freq * ct->ct_len;
  645.     /* # bits saved by using the tree */
  646.     *saved = (totalfreq * srclen) - totalbits;
  647.  
  648.     /* That's all. */
  649.     return IM_OK;
  650.  
  651. #ifdef VALIDATE
  652. badarg:
  653.     fprintf (stderr, "\nError in ct_gencodes: bad argument(s)");
  654.     return IM_BADARG;
  655. #endif /* VALIDATE */
  656. }
  657.  
  658.  
  659. /***********************************************************************
  660.  *
  661.  * Split a portion of a code tree into two pieces of approximately equal
  662.  * total frequency.  This routine calls itself recursively in order to
  663.  * generate the bit strings for the entire code tree.
  664.  */
  665.  
  666. local
  667. ImpErr
  668. ct_split (part, size, freq, prefix, preflen, minbits, maxbits)
  669.     TRDATA *part;               /* start of partition */
  670.     int     size;               /* # elements in partition */
  671.     long    freq;               /* sum of frequencies in partition */
  672.     int     prefix;             /* initial code bits for partition */
  673.     int     preflen;            /* # bits in prefix */
  674.     int     minbits;            /* minimum permissible bit length */
  675.     int     maxbits;            /* maximum permissible bit length */
  676. {   register TRDATA *ct;
  677.     int topmaxbits, botmaxbits, localminbits;
  678.     U_INT topmaxvals, botmaxvals;
  679.     int topsize, botsize;
  680.     long topfreq, botfreq, halffreq, onefreq;
  681.     int n, m, leadzeros;
  682.     int maxshort, minlong;
  683.     ImpErr retcode;
  684.     static maxarray[17] =
  685.         { 8,8,8,8,12,12,14,14,16,16,16,16,16,16,16,16,16 };
  686.  
  687. #ifdef VALIDATE
  688.     if (part == NULL)           goto badarg;
  689.     if (size < 1)               goto badarg;
  690.     if (freq < 0)               goto badarg;
  691.     if (preflen < 0)            goto badarg;
  692.     if (preflen > maxbits)      goto badarg;
  693.     if (minbits < preflen)      goto badarg;
  694.     if (maxbits > 16)           goto badarg;
  695.     if (maxbits < minbits)      goto badarg;
  696.     /*
  697.     putc ('\n', stderr);
  698.     for (n = preflen; n > 0; n--) fprintf (stderr, "   ");
  699.     fprintf (stderr, "ct_split (sz=%d, pr=%04x[%d], min=%d, max=%d)",
  700.              size, prefix, preflen, minbits, maxbits);
  701.     */
  702. #endif /* VALIDATE */
  703.  
  704.     /*
  705.      * If there's only one element in this partition, we simply take
  706.      * the "prefix" value as the code string for the single element.
  707.      * We reverse the bits of the prefix for more efficient output.
  708.      */
  709.     if (size == 1)
  710.     {   part->ct_code = bi_reverse(prefix, preflen);
  711.         part->ct_len  = (U_CHAR)preflen;
  712.         return IM_OK;
  713.     }
  714.  
  715.     /*
  716.      * This partition will be divided into two parts.  The "top" part
  717.      * will have a "1" bit appended to its "prefix" bit string; the
  718.      * "bottom" part will have a "0" bit appended to its "prefix".
  719.      *
  720.      * We need to determine the maximum number of source values which
  721.      * may be assigned to the two partitions.  The first issue to con-
  722.      * sider is that PKUNZIP 1.10's tree-decoding shortcuts require a
  723.      * certain number of leading "0" bits in each code string, depending
  724.      * on its length.  Code strings of 9-12 bits must have at least 4
  725.      * leading zeros; strings of 13 or 14 bits, at least 6 leading
  726.      * zeros; and strings of 15 or 16 bits, at least 8 leading zeros.
  727.      *
  728.      * If the "prefix" is zero, the above limitation is used to restrict
  729.      * the maximum size of the top half of the partition.  The bottom
  730.      * half does not need to be restricted in this way, since it can be
  731.      * extended as far as needed along the path where the "prefix" grows
  732.      * in length but remains all zero.
  733.      */
  734.     botmaxbits = maxbits;
  735.     if (prefix != 0) topmaxbits = maxbits;
  736.     else
  737.     {   for (n = 0, leadzeros = 0x8000;
  738.              n < preflen && (prefix & leadzeros) == 0;
  739.              n++, leadzeros >>= 1) ;
  740.         topmaxbits = maxarray[n];
  741.         if (topmaxbits > maxbits) topmaxbits = maxbits;
  742.     }
  743.     if (topmaxbits < minbits)
  744.     {   fprintf (stderr, "\nError in ct_split: ");
  745.         fprintf (stderr, "topmaxbits(%d) < minbits(%d)",
  746.                  topmaxbits, minbits);
  747.         goto oops;
  748.     }
  749.     if (botmaxbits < minbits)
  750.     {   fprintf (stderr, "\nError in ct_split: ");
  751.         fprintf (stderr, "botmaxbits(%d) < minbits(%d)",
  752.                  botmaxbits, minbits);
  753.         goto oops;
  754.     }
  755.     topmaxvals = 1 << (topmaxbits - preflen - 1);
  756.     n = size >> 1; if (topmaxvals > n) topmaxvals = n;
  757.     botmaxvals = 1 << (botmaxbits - preflen - 1);
  758.     n = size - 1;  if (botmaxvals > n) botmaxvals = n;
  759.     if (topmaxvals + botmaxvals < size)
  760.     {   fprintf (stderr, "\nError in ct_split: ");
  761.         fprintf (stderr, "topmaxvals(%d) + botmaxvals(%d) ",
  762.                  topmaxvals, botmaxvals);
  763.         fprintf (stderr, "< size(%d)", size);
  764.         goto oops;
  765.     }
  766.  
  767.     /*
  768.      * We now split the current partition into two halves of as close
  769.      * to equal frequency as possible.  If the total of all frequencies
  770.      * in the partition is zero, split into two halves of equal size.
  771.      */
  772.     if (freq == 0)
  773.     {   topsize = size >> 1;
  774.         ct = part + topsize;
  775.         topfreq = 0;
  776.     }
  777.     else
  778.     {   halffreq = freq >> 1;           /* half the total frequency */
  779.         m = size >> 1;                  /* half the total elements, */
  780.                                         /*    rounded down          */
  781.         for (topsize = 0, topfreq = 0, ct = part;
  782.              topsize < m && topfreq <= halffreq
  783.                  && (onefreq = ct->ct_freq) > 0;
  784.              topsize++, ct++)
  785.             topfreq += onefreq;
  786.         if (topsize >= 2)
  787.         {   /*
  788.              * If moving one element from the top to the bottom parti-
  789.              * tion would make the two more closely equal in frequency,
  790.              * do it.
  791.              */
  792.             onefreq = (ct-1)->ct_freq;
  793.             if ((topfreq - halffreq) > (halffreq - (topfreq - onefreq)))
  794.                 ct--, topsize--, topfreq -= onefreq;
  795.     }   }
  796.     botsize = size - topsize;
  797.     botfreq = freq - topfreq;
  798.     /* "ct" points to first element in bottom half */
  799.  
  800.     /*
  801.      * The above first-cut attempt to split the partition may not work
  802.      * for one of two reasons.  First, one or the other half may contain
  803.      * too many values (more than "topmaxvals" or "botmaxvals").
  804.      */
  805.     while (topsize > topmaxvals)
  806.     {   onefreq = (--ct)->ct_freq;
  807.         topsize--; topfreq -= onefreq;
  808.         botsize++; botfreq += onefreq;
  809.     }
  810.     while (botsize > botmaxvals)
  811.     {   onefreq = (ct++)->ct_freq;
  812.         topsize++; topfreq += onefreq;
  813.         botsize--; botfreq -= onefreq;
  814.     }
  815.  
  816.     /*
  817.      * Second, the number of bits required to represent the values in
  818.      * each half may violate PKZIP's requirement (implicit in the way
  819.      * trees are compressed in an imploded file) that no code string in
  820.      * the top half may be longer than any code string in the bottom
  821.      * half.
  822.      */
  823.     localminbits = preflen + 1;
  824.     if (localminbits < minbits) localminbits = minbits;
  825.     for (;;)
  826.     {   for (maxshort = preflen + 1, n = 1;
  827.              n < botsize;
  828.              maxshort++, n <<= 1) ;
  829.         if (n > botsize) maxshort--;
  830.         if (maxshort < localminbits) maxshort = localminbits;
  831.         if (maxshort > topmaxbits) maxshort = topmaxbits;
  832.         for (minlong = preflen + 1, n = 1;
  833.              n < topsize;
  834.              minlong++, n <<= 1) ;
  835.         if (minlong <= maxshort) break;
  836.         onefreq = (--ct)->ct_freq;
  837.         topsize--; topfreq -= onefreq;
  838.         botsize++; botfreq += onefreq;
  839.     }
  840.  
  841.     /*
  842.      * Third, the number of elements in the top half must be enough to
  843.      * result in each string having at least "minbits" bits in all.
  844.      */
  845.     n = 1 << (minbits - preflen - 1);
  846.     while (topsize < n)
  847.     {   onefreq = (ct++)->ct_freq;
  848.         topsize++; topfreq += onefreq;
  849.         botsize--; botfreq -= onefreq;
  850.     }
  851.  
  852.     /*
  853.      * Now that the sizes of the two halves of the partition have been
  854.      * finalized, process the top and bottom halves via recursion.
  855.      */
  856.     retcode = ct_split (part, topsize, topfreq,
  857.                         prefix | (1 << (15-preflen)),
  858.                         preflen + 1, localminbits, maxshort);
  859.     if (retcode != IM_OK) return retcode;
  860.     ct = part + topsize;
  861.     retcode = ct_split (ct, botsize, botfreq,
  862.                         prefix, preflen + 1, (int)ct[-1].ct_len, maxbits);
  863.     if (retcode != IM_OK) return retcode;
  864.  
  865.     /* That's all. */
  866.     return IM_OK;
  867.  
  868. #ifdef VALIDATE
  869. badarg:
  870.     fprintf (stderr, "\nError in ct_split: bad argument(s)");
  871.     putchar ('\n'); fflush (stdout); fflush (stderr);
  872.     /* abort (); */
  873.     return IM_BADARG;
  874. #endif /* VALIDATE */
  875.  
  876. oops:
  877. #ifdef VALIDATE
  878.     putchar ('\n'); fflush (stdout); fflush (stderr);
  879.     /* abort (); */
  880. #endif /* VALIDATE */
  881.     return IM_LOGICERR;
  882. }
  883.  
  884.  
  885. /***********************************************************************
  886.  *
  887.  * Sorting function -- descending order by source value frequency.
  888.  *
  889.  * This sorting function is used at the start of the code tree con-
  890.  * struction process, before the bit string values are assigned.
  891.  * To ensure consistent behaviour on all machines, we use the source
  892.  * values as secondary sort key, but this is not mandatory.
  893.  */
  894.  
  895. local
  896. int
  897. ct_fsort (tr1, tr2)
  898.     TRDATA *tr1, *tr2;
  899. {   long d;
  900.     int v;
  901.  
  902.     d = (long) tr1->ct_freq - (long) tr2->ct_freq;
  903.     if (d < 0) return 1;
  904.     if (d > 0) return -1;
  905.     v = (int) tr1->ct_val - (int) tr2->ct_val;
  906.     if (v < 0) return 1;
  907.     if (v > 0) return -1;
  908.     return 0;
  909. }
  910.  
  911.  
  912. /***********************************************************************
  913.  *
  914.  * Sorting function -- ascending order by bit string length; if lengths
  915.  * are the same, ascending order by source value.
  916.  *
  917.  * This sorting function is used after the bit string values have been
  918.  * assigned.  
  919.  */
  920.  
  921. local
  922. int
  923. ct_rsort (cr1, cr2)
  924.     RESORT *cr1, *cr2;
  925. {   int d;
  926.  
  927.     d = (int) cr1->ct_rlen - (int) cr2->ct_rlen;
  928.     if (d > 0) return 1;
  929.     if (d < 0) return -1;
  930.     d = (int) cr1->ct_rval - (int) cr2->ct_rval;
  931.     if (d > 0) return 1;
  932.     if (d < 0) return -1;
  933.     return 0;
  934. }
  935.  
  936.  
  937. /***********************************************************************
  938.  *
  939.  * Allocate the code trees.
  940.  */
  941.  
  942. ImpErr
  943. ct_init ()
  944. {   ImpErr retcode;
  945.     int i;
  946.  
  947. #ifdef DEBUG
  948.     if (256*sizeof(TRDATA) > MA_BUFSIZE*sizeof(MATCH)) return IM_LOGICERR;
  949. #endif /* DEBUG */
  950.  
  951.     retcode = ct_windup ();
  952.         if (retcode != IM_OK) return retcode;
  953.  
  954.     ct_litc_num = 0;
  955.     ct_lit2_num = 0;
  956.     ct_strg_num = 0;
  957.  
  958.     for (i = 255; i >= 0;  i--)
  959.         ct_litc_freq[i] = 0;
  960.     for (i = 63; i >= 0; i--)
  961.         ct_len2_freq[i] = 0, ct_len3_freq[i] = 0,
  962.         ct_dst2_freq[i] = 0, ct_dst3_freq[i] = 0;
  963.  
  964.     retcode = ct_alloc (256, &ct_litc_tree);
  965.     if (retcode != IM_OK) return retcode;
  966.     retcode = ct_alloc  (64, &ct_len2_tree);
  967.     if (retcode != IM_OK) return retcode;
  968.     retcode = ct_alloc  (64, &ct_len3_tree);
  969.     if (retcode != IM_OK) return retcode;
  970.     retcode = ct_alloc  (64, &ct_dst2_tree);
  971.     if (retcode != IM_OK) return retcode;
  972.     retcode = ct_alloc  (64, &ct_dst3_tree);
  973.     if (retcode != IM_OK) return retcode;
  974.  
  975.     return IM_OK;
  976. }
  977.  
  978.  
  979. /***********************************************************************
  980.  *
  981.  * Tally a "string match" data set.  The tally results will be used to
  982.  * determine how large the imploded result will be.
  983.  */
  984.  
  985. ImpErr
  986. ct_tally (ma)
  987.          MATCH *ma;             /* match data to write out */
  988. {   register int ch;
  989.     int dist = ma->ma_dist;
  990.  
  991.     /* Tally up the latest data. */
  992.     if (dist == 0) {                 /* literal character */
  993.             ct_litc_num++;
  994.             ch = ma->l.ma_litc[0];
  995.                 ct_litc_freq[ch]++;
  996.  
  997.     } else if (dist < 0) {           /* 2-character match */
  998.             ct_lit2_num++;
  999.             ch = ma->l.ma_litc[0];
  1000.                 ct_litc_freq[ch]++;
  1001.             ch = ma->l.ma_litc[1];
  1002.                 ct_litc_freq[ch]++;
  1003.             ch = ((-dist-1) >> fd.fd_nbits) & 0x3f;
  1004.                 ct_dst2_freq[ch]++;
  1005.             ct_len2_freq[0]++;
  1006.  
  1007.      } else {                        /* 3-char or longer match */
  1008.             ct_strg_num++;
  1009.             ch = ((dist-1) >> fd.fd_nbits) & 0x3f;
  1010.                 ct_dst3_freq[ch]++;
  1011.          /* We defer the update of ct_dst2_freq and ct_len2_freq until
  1012.           * ct_mktrees:
  1013.           *     ct_dst2_freq[ch]++;
  1014.           * ch = ma->l.ma_length - 2;
  1015.           *     if (ch > 63) ch = 63;
  1016.           *     ct_len2_freq[ch]++;
  1017.           */
  1018.             ch = ma->l.ma_length - 3;
  1019.                 if (ch > 63) ch = 63;
  1020.                 ct_len3_freq[ch]++;
  1021.     }
  1022.  
  1023.     /* That's all. */
  1024.     return IM_OK;
  1025. }
  1026.  
  1027.  
  1028. /***********************************************************************
  1029.  *
  1030.  * Construct all code trees, and then determine how big the imploded
  1031.  * file will be under both "literal tree" and "no literal tree" con-
  1032.  * ditions.  Choose the best option.
  1033.  */
  1034.  
  1035. ImpErr
  1036. ct_mktrees ()
  1037. {   U_CHAR *c;
  1038.     ImpErr retcode;
  1039.     register long sum;
  1040.     long len2, len3;
  1041.     int n;
  1042.  
  1043.     /* ct_tally did not update ct_dst2_freq and ct_len2_freq for matches of
  1044.      * length > 2, so correct this now.
  1045.      */
  1046.     for (n = 62; n >= 0; n--) {
  1047.         ct_dst2_freq[n] += ct_dst3_freq[n];
  1048.         ct_len2_freq[n+1] += ct_len3_freq[n];
  1049.     }
  1050.     ct_dst2_freq[63] += ct_dst3_freq[63];
  1051.     ct_len2_freq[63] += ct_len3_freq[63];
  1052.  
  1053.     /*
  1054.      * Construct the code trees and see how much space each will save.
  1055.      *
  1056.      * It is conceivable that a tree could result in a negative savings
  1057.      * if its compressed form is sufficiently long.
  1058.      *
  1059.      * We need to construct the ZIP-file compressed representation of
  1060.      * each tree in order to figure out how much space it will take.
  1061.      * However, we don't save these tree representations now; rather,
  1062.      * we'll wait until later and reconstruct the representations for
  1063.      * whichever two (or three) trees we really need for the output.
  1064.      */
  1065. #ifdef IMPDEBUG
  1066.     treename = (char *)NULL;
  1067. #endif /* IMPDEBUG */
  1068.  
  1069.     /* literal code tree */
  1070.     retcode = ct_loadf    (ct_litc_tree,  ct_litc_freq);
  1071.         if (retcode != IM_OK) return retcode;
  1072.     retcode = ct_gencodes (ct_litc_tree, 1, 16, &ct_litc_saved);
  1073.         if (retcode != IM_OK) return retcode;
  1074.     retcode = ct_ziprep   (ct_litc_tree, &c);
  1075.         if (retcode != IM_OK) return retcode;
  1076.     ct_litc_saved -= (int) (c[0]+2) * 8;
  1077.  
  1078.     /* length code tree (2) */
  1079.     retcode = ct_loadf    (ct_len2_tree,  ct_len2_freq);
  1080.         if (retcode != IM_OK) return retcode;
  1081.     retcode = ct_gencodes (ct_len2_tree, 1, 16, &ct_len2_saved);
  1082.         if (retcode != IM_OK) return retcode;
  1083.     retcode = ct_ziprep   (ct_len2_tree, &c);
  1084.         if (retcode != IM_OK) return retcode;
  1085.     ct_len2_saved -= (int) (c[0]+2) * 8;
  1086.  
  1087.     /* length code tree (3) */
  1088.     retcode = ct_loadf    (ct_len3_tree,  ct_len3_freq);
  1089.         if (retcode != IM_OK) return retcode;
  1090.     retcode = ct_gencodes (ct_len3_tree, 1, 16, &ct_len3_saved);
  1091.         if (retcode != IM_OK) return retcode;
  1092.     retcode = ct_ziprep   (ct_len3_tree, &c);
  1093.         if (retcode != IM_OK) return retcode;
  1094.     ct_len3_saved -= (int) (c[0]+2) * 8;
  1095.  
  1096.     /* distance code tree (2) */
  1097.     retcode = ct_loadf    (ct_dst2_tree,  ct_dst2_freq);
  1098.         if (retcode != IM_OK) return retcode;
  1099.     retcode = ct_gencodes (ct_dst2_tree, 1,  8, &ct_dst2_saved);
  1100.         if (retcode != IM_OK) return retcode;
  1101.     retcode = ct_ziprep   (ct_dst2_tree, &c);
  1102.         if (retcode != IM_OK) return retcode;
  1103.     ct_dst2_saved -= (int) (c[0]+2) * 8;
  1104.  
  1105.     /* distance code tree (3) */
  1106.     retcode = ct_loadf    (ct_dst3_tree,  ct_dst3_freq);
  1107.         if (retcode != IM_OK) return retcode;
  1108.     retcode = ct_gencodes (ct_dst3_tree, 1,  8, &ct_dst3_saved);
  1109.         if (retcode != IM_OK) return retcode;
  1110.     retcode = ct_ziprep   (ct_dst3_tree, &c);
  1111.         if (retcode != IM_OK) return retcode;
  1112.     ct_dst3_saved -= (int) (c[0]+2) * 8;
  1113.  
  1114.     /*
  1115.      * Determine how big the compressed file will be
  1116.      * with, and without, a literal character tree.
  1117.      */
  1118.  
  1119.     /* compressed length (no literal tree) */
  1120.     sum  = ct_litc_num + ct_lit2_num + ct_strg_num;    /* initial bit */
  1121.     sum += ct_litc_num * 8;                          /* literal bytes */
  1122.     sum += (ct_lit2_num+ct_strg_num) * 6 - ct_len2_saved;  /* lengths */
  1123.     sum += 8 * ct_len2_freq[63];                  /* oversize lengths */
  1124.     sum += (ct_lit2_num+ct_strg_num) * (fd.fd_nbits+6)
  1125.             - ct_dst2_saved;                             /* distances */
  1126.     len2 = (sum+7) / 8;                           /* convert to bytes */
  1127.  
  1128.     /* compressed length (with literal tree) */
  1129.     sum  = ct_litc_num + 2*ct_lit2_num + ct_strg_num;  /* initial bit */
  1130.     sum += (ct_litc_num+2*ct_lit2_num)*8 - ct_litc_saved;/* lit bytes */
  1131.     sum += ct_strg_num * 6 - ct_len3_saved;                /* lengths */
  1132.     sum += 8 * ct_len3_freq[63];                  /* oversize lengths */
  1133.     sum += ct_strg_num * (fd.fd_nbits+6) - ct_dst3_saved;   /* dist's */
  1134.     len3 = (sum+7) / 8;                           /* convert to bytes */
  1135.  
  1136.     /*
  1137.      * PKUNZIP 1.10 requires that the source value 255 in a "literal"
  1138.      * tree must be represented by a bit string of length >= 10.  The
  1139.      * literal tree was already adjusted to ensure that the value 255
  1140.      * was given a bit string of length 10 or greater if possible.  If
  1141.      * this did not succeed -- which would only happen if the longest
  1142.      * bit string in the literal tree were of length 8 or 9 -- then the
  1143.      * literal tree cannot be used.  In such a case, not much would be
  1144.      * gained by using it anyway, so there's little reason to be upset.
  1145.      */
  1146.     if (ct_table[ct_litc_tree].ct_array[255].ct_len < 10)
  1147.         len3 = len2;
  1148.  
  1149.     /*
  1150.      * Choose the method of compression which will use the least space
  1151.      * for this particular file.  The possibilities are:  use a literal
  1152.      * character tree; or, don't use a literal character tree.
  1153.      */
  1154.     if (len2 <= len3)
  1155.     {   fd.fd_method = NO_LITERAL_TREE;
  1156.         fd.fd_clen   = len2;
  1157.         lit_tree     = -1;
  1158.         len_tree     = ct_len2_tree;
  1159.         dst_tree     = ct_dst2_tree;
  1160.         retcode = ct_free (ct_litc_tree);
  1161.             if (retcode != IM_OK) return retcode;
  1162.         retcode = ct_free (ct_dst3_tree);
  1163.             if (retcode != IM_OK) return retcode;
  1164.         retcode = ct_free (ct_len3_tree);
  1165.             if (retcode != IM_OK) return retcode;
  1166.     }
  1167.     else
  1168.     {   fd.fd_method = LITERAL_TREE;
  1169.         fd.fd_clen   = len3;
  1170.         lit_tree     = ct_litc_tree;
  1171.         len_tree     = ct_len3_tree;
  1172.         dst_tree     = ct_dst3_tree;
  1173.         retcode = ct_free (ct_dst2_tree);
  1174.             if (retcode != IM_OK) return retcode;
  1175.         retcode = ct_free (ct_len2_tree);
  1176.             if (retcode != IM_OK) return retcode;
  1177.     }
  1178.  
  1179.     /* That's all. */
  1180.     return IM_OK;
  1181. }
  1182.  
  1183.  
  1184. /***********************************************************************
  1185.  *
  1186.  * Output the code trees.
  1187.  */
  1188.  
  1189. ImpErr
  1190. ct_wrtrees (outfp)
  1191.     FILE *outfp;                        /* output file */
  1192. {   ImpErr retcode;
  1193.     U_CHAR *c;
  1194.  
  1195.     /* Output the literal tree, if any. */
  1196. #ifdef IMPDEBUG
  1197.     treename = "Literal";
  1198. #endif /* IMPDEBUG */
  1199.     if (lit_tree >= 0)
  1200.     {   retcode = ct_ziprep (lit_tree, &c);
  1201.             if (retcode != IM_OK) return retcode;
  1202.         if (zfwrite ((char *) c, (int) (c[0]+2), 1, outfp) != 1)
  1203.             return IM_IOERR;
  1204.     }
  1205.  
  1206.     /* Output the length tree. */
  1207. #ifdef IMPDEBUG
  1208.     treename = "Length";
  1209. #endif /* IMPDEBUG */
  1210.     retcode = ct_ziprep (len_tree, &c);
  1211.         if (retcode != IM_OK) return retcode;
  1212.     if (zfwrite ((char *) c, (int) (c[0]+2), 1, outfp) != 1)
  1213.         return IM_IOERR;
  1214.  
  1215.     /* Output the distance tree. */
  1216. #ifdef IMPDEBUG
  1217.     treename = "Distance";
  1218. #endif /* IMPDEBUG */
  1219.     retcode = ct_ziprep (dst_tree, &c);
  1220.         if (retcode != IM_OK) return retcode;
  1221.     if (zfwrite ((char *) c, (int) (c[0]+2), 1, outfp) != 1)
  1222.         return IM_IOERR;
  1223.  
  1224.     return IM_OK;
  1225. }
  1226.  
  1227. /* Macros for outputting bit string. */
  1228.  
  1229. #define OUTBITS(value,length) \
  1230.         {   retcode = bi_rlout ((int) (value), (int) (length)); \
  1231.                 if (retcode != IM_OK) return retcode; \
  1232.         }
  1233. #define OUTCODE(value,tree) \
  1234.         {   ct_lookup (tree, value, bitstring, bitlength); \
  1235.             retcode = bi_rlout (bitstring, bitlength); \
  1236.                 if (retcode != IM_OK) return retcode; \
  1237.         }
  1238.  
  1239. /***********************************************************************
  1240.  *
  1241.  * Output the body of the file in imploded form.
  1242.  */
  1243. ImpErr
  1244. ct_wrdata (outfp)
  1245.          FILE *outfp;                   /* output (ZIP) file */
  1246. {   MATCH *ma;
  1247.     ImpErr retcode;
  1248.     register int minmatch;
  1249.     int bitstring, bitlength;
  1250.     int bitmask = (1 << (fd.fd_nbits+1))-1;
  1251.     /* Used to select the bottom 6 or 7 bits of a distance, which are
  1252.      * output literally, plus 1 bit marking a distance
  1253.      */
  1254.     int matches;
  1255. #ifdef  IMPDEBUG
  1256.     long srcpos;
  1257. #endif  /* IMPDEBUG */
  1258.  
  1259.     /* Determine the minimum match length. */
  1260.     minmatch = (lit_tree >= 0) ? 3 : 2;
  1261.  
  1262.     /* Prepare the I/O. */
  1263.     if (tflush (fd.fd_temp) != 0) return IM_IOERR;
  1264.     trewind (fd.fd_temp);
  1265.     retcode = bi_init (outfp);
  1266.         if (retcode != IM_OK) return retcode;
  1267.  
  1268. #ifdef  IMPDEBUG
  1269.         srcpos = 0;
  1270.         fprintf (stderr, "\nImploded output:\n");
  1271. #endif  /* IMPDEBUG */
  1272.  
  1273.     /* Read and process data from the temporary file. */
  1274.     while ((matches =
  1275.        tread ((char *) ma_buf, sizeof(MATCH), MA_BUFSIZE, fd.fd_temp)) > 0)
  1276.        for (ma = ma_buf; matches > 0; ma++, matches--)
  1277.     {
  1278.         int dist = ma->ma_dist;
  1279.         int len = 0;
  1280.  
  1281. #ifdef  IMPDEBUG
  1282.         fprintf (stderr, "%8ld: ", srcpos);
  1283. #endif  /* IMPDEBUG */
  1284.  
  1285.         if (dist < 0) {
  1286.             dist = -dist, len = 2;
  1287.         } else if (dist > 0) {
  1288.             len = ma->l.ma_length;
  1289.         }
  1290.  
  1291.         /* Output distance and length if enough characters match. */
  1292.         if (len >= minmatch)
  1293.         {   /* "matched string" header bit (0) */
  1294. #ifdef  IMPDEBUG
  1295.             fprintf (stderr, "str (dst=%d,len=%d)  ",
  1296.                      dist, len);
  1297.             srcpos += len;
  1298. #endif  /* IMPDEBUG */
  1299.  
  1300.             /* ouput one zero bit then the distance */
  1301.             dist--;
  1302.             OUTBITS ((dist << 1) & bitmask, fd.fd_nbits + 1);
  1303.             OUTCODE (dist >> fd.fd_nbits, dst_tree);
  1304.  
  1305.             /* length -- depends on how it compares to maximum */
  1306.             len -= minmatch;
  1307.             if (len >= 63)
  1308.             {   /* big length -- output code for 63, then surplus */
  1309.                 OUTCODE (63, len_tree);
  1310.                 OUTBITS ((len - 63), 8);
  1311.             }
  1312.             else
  1313.             {   /* small length -- output code */
  1314.                 OUTCODE (len, len_tree);
  1315.         }   }
  1316.         else if (lit_tree >= 0)
  1317.         {   /* first or single literal -- header bit (1) plus char */
  1318. #ifdef  IMPDEBUG
  1319.             fprintf (stderr, "lit (val=%02x)  ",
  1320.                      ma->l.ma_litc[0] & 0xff);
  1321.             srcpos++;
  1322. #endif  /* IMPDEBUG */
  1323.             OUTBITS (1, 1);
  1324.             OUTCODE (ma->l.ma_litc[0], lit_tree);
  1325.             if (len == 2)
  1326.             {   /* second literal -- header bit (1) plus char */
  1327. #ifdef  IMPDEBUG
  1328.                 fprintf (stderr, "\n%8ld: lit (val=%02x)  ",
  1329.                          srcpos, ma->l.ma_litc[1] & 0xff);
  1330.                 srcpos++;
  1331. #endif  /* IMPDEBUG */
  1332.                 OUTBITS (1, 1);
  1333.                 OUTCODE (ma->l.ma_litc[1], lit_tree);
  1334.         }   }
  1335.         else
  1336.         {   /* single literal -- header bit (1) plus char */
  1337. #ifdef  IMPDEBUG
  1338.             fprintf (stderr, "lit (val=%02x)  ",
  1339.                      ma->l.ma_litc[0] & 0xff);
  1340.             srcpos++;
  1341. #endif  /* IMPDEBUG */
  1342.             OUTBITS ((ma->l.ma_litc[0] << 1) + 1, 9);
  1343.         }
  1344. #ifdef  IMPDEBUG
  1345.         putc ('\n', stderr);
  1346. #endif  /* IMPDEBUG */
  1347.     }
  1348.  
  1349.     /* Make sure we hit EOF on input without an error. */
  1350.     if (terror (fd.fd_temp)
  1351. #ifndef MINIX
  1352. #ifndef __TURBOC__      /* TurboC 2.0 does not set the EOF flag (?) */
  1353.         || !teof (fd.fd_temp)
  1354. #endif /* !__TURBOC__ */
  1355. #endif /* !MINIX */
  1356.        )
  1357.       return IM_IOERR;
  1358.     retcode = bi_windup ();
  1359.         if (retcode != IM_OK) return retcode;
  1360.  
  1361.     /* That's all. */
  1362.     return IM_OK;
  1363. }
  1364.  
  1365. #undef  OUTBITS
  1366. #undef  OUTCODE
  1367.  
  1368.  
  1369. /***********************************************************************
  1370.  *
  1371.  * Deallocate all code trees.
  1372.  */
  1373.  
  1374. ImpErr
  1375. ct_windup ()
  1376. {   int n;
  1377.     static windup_already_called = 0;
  1378.     ImpErr retcode;
  1379.  
  1380.     if (windup_already_called)
  1381.     {   /* Discard any old code trees. */
  1382.         for (n = 0; n < MAXTREES; n++)
  1383.         {   if (ct_table[n].ct_array != NULL)
  1384.             {   retcode = ct_free (n);
  1385.                 if (retcode != IM_OK) return retcode;
  1386.     }   }   }
  1387.     else
  1388.     {   /* Initialize the list of active code trees. */
  1389.         for (n = 0; n < MAXTREES; n++)
  1390.         {   ct_table[n].ct_array = NULL;
  1391.             ct_table[n].ct_size  = 0;
  1392.         }
  1393.         windup_already_called = 1;
  1394.     }
  1395.  
  1396.     /* That's all. */
  1397.     return IM_OK;
  1398. }
  1399.  
  1400.  
  1401. /**********************************************************************/
  1402.